#ifndef __BINARYTREE_H__
#define __BINARYTREE_H__

using ElementType = void*;

class BinaryTree
{

public:
    BinaryTree();
    BinaryTree(void(*showptr)(const ElementType&),int(*cmpptr)(const ElementType&,const ElementType&));
    ~BinaryTree();
    void Insert(const ElementType &element);
    void show();
    ElementType* Find(const ElementType&element);
    void RemoveByElement(const ElementType&element);
    bool IsComTree();
    void Count();
private:
    struct TreeNode
    {

        TreeNode(const ElementType &element)
        {
            value = element;
            left = right = parent = nullptr;
        }

        ElementType value;
        TreeNode *left;
        TreeNode *right;
        TreeNode *parent;
    };
    TreeNode *InsertNode(TreeNode *node, const ElementType &element);
    void PrevTravel(TreeNode *node);
    void MidTravel(TreeNode *node);
    void PostTravel(TreeNode *node);
    void FreeNode(TreeNode*node);
    ElementType*FindNode(TreeNode*node,const ElementType&element);
    TreeNode* Remove(TreeNode*node,const ElementType&element);
    TreeNode *root;
    TreeNode*GetMinNode(TreeNode*node);
    TreeNode*RotateRight(TreeNode*node);
    TreeNode*RotateLeft(TreeNode*node);
    TreeNode*RotateLeftRight(TreeNode*node);
    TreeNode*RotateRightLeft(TreeNode*node);
    int GetNodeHight(TreeNode*node);
    int LRDev(TreeNode*node);
    void (*showptr)(const ElementType& value);
    int  (*cmpptr)(const ElementType&element1,const ElementType&element2);
    bool IsComTree1(TreeNode*node);
    int Count1(TreeNode*node);
    
};

#endif